package Ep06_BinaryTree.BT23_0098;

import Ep06_BinaryTree.TreeNode;

import java.util.ArrayList;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/6/14 10:04
 * 说明：
 *      0098 验证一个树是不是二叉搜索树BST —— 暴力解法
 * 思路：
 *      先递归，中序遍历成一个动态数组，如果是BTS，这个数组中的元素应该是升序的
 *      再判断这个数组中的元素是否严格升序 即可。
 */

public class Mine {
    public boolean isValidBST(TreeNode root) {
        ArrayList<Integer> arr = new ArrayList<>();
        ArrayList<Integer> root2Arr = recursion(root, arr); // 如果是BST，中序遍历应该得到顺序数组
        // 判断是否是顺序数组即可
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i-1) >= arr.get(i)) {
                return false;
            }
        }
            return true;
    }

    // 遍历方法
    private ArrayList<Integer> recursion(TreeNode root, ArrayList<Integer> arr) {
        if (root == null) return arr;
        recursion(root.left, arr);
        arr.add(root.val);
        recursion(root.right, arr);
        return arr;
    }
}
